package structure.linkedList;


import java.util.HashMap;

/**
 * 地址：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
 * <p>
 * 题目：剑指 Offer 52. 两个链表的第一个公共节点
 * <p>
 输入两个链表，找出它们的第一个公共节点。

 * <p>
 * 示例1：
 * <p>
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 */
public class Leetcode_Sword_Offer_52 {
    public static void main(String[] args) {

        ListNode node = new ListNode(1);
        node.next = new ListNode(8);
        node.next.next = new ListNode(4);
        node.next.next.next = new ListNode(5);
    }

    /**
     * 解法1：
     * 思路： 使用 HashMap 来存储值和链表节点,
     * 分别循环两个 链表，第一个链表循环进行记录，第二个链表循环进行比对。
     * <p>
     * 时间复杂度：O(N+M)
     * 空间复杂度：O(1)，没有使用额外的空间
     * <p>
     * <p>
     * 执行结果：通过
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.6 MB, 在所有 Java 提交中击败了95.75%的用户
     * <p>
     *
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashMap<ListNode, ListNode> map = new HashMap<>();
        ListNode l1 = headA, l2 = headB;
        while (l1 != null) {
            map.put(l1, l1);
            l1 = l1.next;
        }
        while (l2 != null) {
            if (map.get(l2) != null) {
                return l2;
            }
            l2 = l2.next;
        }
        return null;

    }

}
